#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <string.h>

#include "fs.h"
#include "disk.h"


// Return 1 if bit at position index in array is set to 1
int bit_isset(uint32_t *array, int index)
{
    uint32_t b = array[index/32];
    uint32_t m = (1 << (index % 32));
    return (b & m) == m;
}

// Set bit at position index in array to 1
void bit_set(uint32_t *array, int index)
{
    uint32_t b = array[index/32];
    uint32_t m = (1 << (index % 32));
    array[index/32] = (b | m);
}

// Clear bit at position index in array
void bit_clear(uint32_t *array, int index)
{
    uint32_t b = array[index/32];
    uint32_t m = (1 << (index % 32));
    array[index/32] = (b & ~m);
}

// read from a ext2 block
void read_disk(char *buf, uint32_t block_num)
{
    disk_read_block(block_num*2, buf);
    disk_read_block(block_num*2 + 1, buf + DEVICE_BLOCK_SIZE);
}

// write to a ext2 block
void write_disk(char *buf, uint32_t block_num)
{
    disk_write_block(block_num * 2, buf);
    disk_write_block(block_num * 2 + 1, buf + DEVICE_BLOCK_SIZE);
}


/**
 * @brief get a inode by inode number
 * 
 * @param inode :the struct to store inode information
 * @param inum :inode number
 */
void read_inode(inode_t* inode, uint32_t inum)
{
    inode_t* tmp;
    char *buf;

    // read a block from disk
    buf = (char*)malloc(DEVICE_BLOCK_SIZE * 2 + 1);
    read_disk(buf, 1 + inum/32);

    tmp = (inode_t*)(buf + (inum % 32) * sizeof(inode_t));
    memcpy(inode, tmp, sizeof(inode_t));

    free(buf);
}


/**
 * @brief write a inode by inode number
 * 
 * @param inode :the struct storing inode information
 * @param inum :inode number
 */
void write_inode(const inode_t* inode, uint32_t inum)
{
    inode_t* tmp;
    char *buf;

    // read a block from disk
    buf = (char*)malloc(DEVICE_BLOCK_SIZE * 2 + 1);
    read_disk(buf, 1 + inum/32);

    tmp = (inode_t*)(buf + (inum % 32) * sizeof(inode_t));
    memcpy(tmp, inode, sizeof(inode_t));

    // write back
    write_disk(buf, 1 + inum/32);

    free(buf);
}


/**
 * @brief get a directory by block_num and directoy rank
 * 
 * @param dir_item :the struct to store directory item information
 * @param block_num :block number
 * @param dir_num :directoy rank in a block
 */
void read_dir_item(dir_item_t* dir_item, uint32_t block_num, int dir_num)
{
    dir_item_t* tmp;
    char *buf;

    // read a block from disk
    buf = (char*)malloc(DEVICE_BLOCK_SIZE * 2 + 1);
    read_disk(buf, block_num);

    tmp = (dir_item_t*)(buf + dir_num * sizeof(dir_item_t));
    memcpy(dir_item, tmp, sizeof(dir_item_t));

    free(buf);
}


/**
 * @brief write a directory by block_num and directoy rank
 * 
 * @param dir_item :the struct storing directory item information
 * @param block_num :block number
 * @param dir_num :directoy rank in a block
 */
void write_dir_item(const dir_item_t* dir_item, uint32_t block_num, int dir_num)
{
    dir_item_t* tmp;
    char *buf;

    // read a block from disk
    buf = (char*)malloc(DEVICE_BLOCK_SIZE * 2 + 1);
    read_disk(buf, block_num);

    tmp = (dir_item_t*)(buf + dir_num * sizeof(dir_item_t));
    memcpy(tmp, dir_item, sizeof(dir_item_t));

    // write back
    write_disk(buf, block_num);

    free(buf);
}


// find a free bit in map
uint32_t find_free_map(uint32_t map[], int len)
{
    int i, j;

    for (i = 0; i < len; i++)
        if(map[i] ^ MAX_UINT32) break;

    if(i == len)
        return 0;

    for (j = i*32; j < (i+1)*32; j++)
        if(!bit_isset(map, j))  return j;
}


/**
 * @brief get a free inode number not distributed
 * 
 * @return uint32_t free inode number. if no free inode, return 0
 */
uint32_t find_free_inode()
{
    uint32_t inum;
    char *buf;
    sp_block *spb;

    buf = (char*)malloc(DEVICE_BLOCK_SIZE * 2 + 1);
    read_disk(buf, 0);
    spb = (sp_block*)buf;

    inum = find_free_map(spb->inode_map, INODE_MAP_LEN);

    free(buf);
    return inum;
}


/**
 * @brief get a free block number not distributed
 * 
 * @return uint32_t free block number. if no free block, return 0
 */
uint32_t find_free_block()
{
    uint32_t inum;
    char *buf;
    sp_block *spb;

    buf = (char*)malloc(DEVICE_BLOCK_SIZE * 2 + 1);
    read_disk(buf, 0);
    spb = (sp_block*)buf;

    inum = find_free_map(spb->block_map, BLOCK_MAP_LEN);

    free(buf);
    return inum;
}


/**
 * @brief check if file already exists in data blocks of a directory
 * 
 * @param block_point :data block pointers of a directoy
 * @param file_name :checked file name
 * @return int 1 for existing, 0 for not
 */
int check_name(uint32_t block_point[], char *file_name)
{
    int i, j;
    dir_item_t dir_item;

    for(i = 0; i < 6; i++)
    {
        if(block_point[i] < 33 || block_point[i] >= MAX_BLOCK)    //create a new block to store the directory item
            continue;

        for(j = 0; j < 2*DEVICE_BLOCK_SIZE / sizeof(dir_item_t); j++)
        {
            read_dir_item(&dir_item, block_point[i], j);
            
            if(dir_item.valid == 0)
                continue;

            if(strcmp(dir_item.name, file_name) == 0)
                return 1;
        }
    }
    return 0;
}


/**
 * @brief create a new file or directory under a directory
 * 
 * @param p_inum :parent diectory inode number
 * @param file_name :file name
 * @param file_type :0 for file, 1 for directory
 * @return uint32_t return inode number. return 0 for failure
 */
uint32_t create_fd(uint32_t p_inum, char *file_name, uint16_t file_type)
{
    int i, j;
    int set_item = 0;
    char *buf;
    sp_block *spb;
    inode_t p_inode;
    inode_t *inode;
    dir_item_t dir_item;
    int dir_num = -1;
    uint32_t block_num = 0;
    uint32_t f_inum;

    if(p_inum <= 0)
        return 0;

    if((f_inum = find_free_inode()) <= 0)
    {
        printf("No free inode!\n");
        return 0;
    }

    // update parent information
    read_inode(&p_inode, p_inum);

    if(p_inode.file_type == T_FILE)
    {
        printf("cannot create a file or directory under a file!\n");
        return 0;
    }
    if(p_inode.size >= 6*2*DEVICE_BLOCK_SIZE)
    {
        printf("No more space for current directory!\n");
        return 0;
    }
    p_inode.size += sizeof(dir_item_t);

    // check if having same name
    if(check_name(p_inode.block_point, file_name))
    {
        printf("Cannot create \'%s\': File exits\n", file_name);
        return 0;
    }

    // find a free dir_item
    for(i = 0; i < 6; i++)
    {
        if(p_inode.block_point[i] < 33 || p_inode.block_point[i] >= MAX_BLOCK)    //create a new block to store the directory item
        {
            if((block_num = find_free_block()) < 0)
            {
                printf("No free block!\n");
                return 0;
            }
            p_inode.block_point[i] = block_num;
            dir_num = 0;
        }
        else    // find a invalid item
        {  
            for(j = 0; j < 2*DEVICE_BLOCK_SIZE / sizeof(dir_item_t); j++)
            {
                read_dir_item(&dir_item, p_inode.block_point[i], j);

                if(dir_item.valid == 0)
                {   
                    dir_num = j;
                    break;
                }
            }
        }
        
        if(dir_num >= 0)
        {
            dir_item.inode_id = f_inum;
            dir_item.valid = 1;
            dir_item.type = file_type;
            strcpy(dir_item.name, file_name);

            write_dir_item(&dir_item, p_inode.block_point[i], dir_num);
            break;
        }
    }
    write_inode(&p_inode, p_inum);


    // update super block
    buf = (char*)malloc(DEVICE_BLOCK_SIZE * 2 + 1);
    read_disk(buf, 0);
    spb = (sp_block*)buf;
    spb->free_inode_count -= 1;
    if(block_num > 0)
    {
        bit_set(spb->block_map, block_num);
        spb->free_block_count -= 1;
    }
    bit_set(spb->inode_map, f_inum);
    if(file_type == T_DIRECTORY)
        spb->dir_inode_count += 1;  
    write_disk(buf, 0);
    free(buf);


    // update file inode
    inode_t f_inode;
    f_inode.size = 0;
    f_inode.file_type = file_type;
    f_inode.link = 1;
    for(i = 0; i < 6; i++)
        f_inode.block_point[i] = 0;
    write_inode(&f_inode, f_inum);

    return f_inum;
}


/**
 * @brief copy a file
 * 
 * @param src_inum :source file inode number
 * @param dst_pinum :inode number of parent directory of destination file 
 * @param dst_name :destination file name
 * @return uint32_t new file(destination file) inode number. return 0 for failure
 */
uint32_t copy_file(uint32_t src_inum, uint32_t dst_pinum, char *dst_name)
{
    int i;
    char *buf;
    char *block_buf;
    sp_block *spb;
    inode_t src_inode;
    inode_t dst_inode;
    uint32_t f_inum;
    uint32_t block_num = 0;

    read_inode(&src_inode, src_inum);

    if(src_inode.file_type == T_DIRECTORY)
    {
        printf("cannot copy a directory\n");
        return 0;
    }

    f_inum = create_fd(dst_pinum, dst_name, T_FILE);
    if(f_inum <= 0)
    {
        printf("failed to create file\n");
        return 0;
    }

    // update file inode
    dst_inode.size = src_inode.size;
    dst_inode.file_type = src_inode.file_type;
    dst_inode.link = src_inode.file_type;

    block_buf = (char*)malloc(DEVICE_BLOCK_SIZE * 2 + 1);
    for(i = 0; i < 6; i++)
    {
        if(src_inode.block_point[i] < 33 || src_inode.block_point[i] >= MAX_BLOCK)
            continue;
        if((block_num = find_free_block()) <= 0)
        {
            printf("No free block!\n");
            free(block_buf);
            return 0;
        }
        dst_inode.block_point[i] = block_num;
        read_disk(block_buf, src_inode.block_point[i]);
        write_disk(block_buf, dst_inode.block_point[i]);
    }
    write_inode(&dst_inode, f_inum);
    free(block_buf);

    // update super block
    buf = (char*)malloc(DEVICE_BLOCK_SIZE * 2 + 1);
    read_disk(buf, 0);
    spb = (sp_block*)buf;
    for(i = 0; i < 6; i++)
    {
        if(dst_inode.block_point[i] < 33 || dst_inode.block_point[i] >= MAX_BLOCK)
            continue;
        bit_set(spb->block_map, dst_inode.block_point[i]);
        spb->free_block_count -= 1;
    }
    write_disk(buf, 0);
    free(buf);
    
    return f_inum;
}


/**
 * @brief list items in a directory
 * 
 * @param inode_num :inode number of the directory
 * @return uint32_t 
 */
uint32_t list_dir(uint32_t inode_num)
{
    int i, j;
    int flag = 0;
    inode_t inode;
    dir_item_t dir_item;

    
    read_inode(&inode, inode_num);
    if(inode.file_type == T_FILE)
    {
        printf("Can't list items in a file!\n");
        return 0;
    }

    for(i = 0; i < 6; i++)
    {
        if(inode.block_point[i] < 33 || inode.block_point[i] >= MAX_BLOCK)
            continue;

        for(j = 0; j < 2*DEVICE_BLOCK_SIZE / sizeof(dir_item_t); j++)
        {
            read_dir_item(&dir_item, inode.block_point[i], j);
            
            if(dir_item.valid == 0)
                continue;

            if(!flag)
            {
                printf("   Inode Type Name\n");
                flag = 1;
            }
            printf("%8d %4d %s\n", dir_item.inode_id, dir_item.type, dir_item.name);
        }
    }

    return 0;
}


/**
 * @brief get inode from a path
 * 
 * @param path :the path of the file or directory
 * @return uint32_t :inode number of the path. return 0 for failure
 */
uint32_t open_path(char *path)
{
    // search path from root
    if(path[0] == '/')
        return open_by_inode(2, path+1);
    else 
        return open_by_inode(2, path);
}


/**
 * @brief search path in parent directory
 * 
 * @param inum :parent inode number
 * @param path :the path of the file or directory
 * @return uint32_t inode number of the path. return 0 for failure
 */
uint32_t open_by_inode(uint32_t inum, char *path)
{
    char *p;
    inode_t inode;
    dir_item_t dir_item;
    int i, j;
    int is_dir = 0;
    // uint32_t block_point[6];

    if(path[0] == 0)
        return inum;
    
    // get sub-path
    p = path;
    while(p[0] != '/' && p[0] != 0)
        p++;

    read_inode(&inode, inum);

    for(i = 0; i < 6; i++)
    {
        if(inode.block_point[i] < 33 || inode.block_point[i] >= MAX_BLOCK)
            continue;

        for(j = 0; j < 2*DEVICE_BLOCK_SIZE / sizeof(dir_item_t); j++)
        {
            read_dir_item(&dir_item, inode.block_point[i], j);
            
            if(dir_item.valid == 0)
                continue;

            if(*p == '/')
            {
                is_dir = 1;
                *p = 0;
                p++;
            }

            if(strcmp(dir_item.name, path) == 0)
            {
                // check if it is a directory
                if(is_dir && dir_item.type != T_DIRECTORY)
                {
                    printf("cannot access \'%s\': not a directory!\n", path);
                    return 0;
                }

                inum = dir_item.inode_id;
                
                return open_by_inode(inum, p);
            }
        }
    }
    printf("cannot access \'%s\': no such file or directory!\n", path);
    return 0;
}


/**
 * @brief build and format a EXT2 file system
 * 
 */
void init_file_system()
{
    char *buf;
    sp_block *spb;
    inode_t root_inode;
    uint32_t i;

    
    buf = (char*)malloc(DEVICE_BLOCK_SIZE * 2 + 1);

    // initialize super block
    read_disk(buf, 0);
    spb = (sp_block*)buf;

    spb->magic_num = MAGIC_NUMBER;
    spb->free_block_count = MAX_BLOCK - 33;
    spb->free_inode_count = MAX_INODE - 1;
    spb->dir_inode_count = 1;

    for (i = 0; i < BLOCK_MAP_LEN; i++)
    {
        spb->block_map[i] = 0;
    }
    for (i = 0; i <= 32; i++)
    {
        bit_set(spb->block_map, i);
    }

    for (i = 0; i < INODE_MAP_LEN; i++)
    {
        spb->inode_map[i] = 0;
    }
    for (i = 0; i <= 2; i++)
    {
        bit_set(spb->inode_map, i);
    }
    write_disk(buf, 0);
    free(buf);


    // initialize root directory
    root_inode.size = 0;
    root_inode.link = 1;
    root_inode.file_type = T_DIRECTORY;
    write_inode(&root_inode, 2);
}


/**
 * @brief boot the file system, and load the virtual disk 
 * 
 */
void boot_loader()
{
    char *buf;
    sp_block *spb;
    char format_op = 'x';

    if(open_disk() < 0)
    {
        printf("Open disk failed!\n");
        exit(-1);
    }

    buf = (char*)malloc(DEVICE_BLOCK_SIZE * 2 + 1);
    read_disk(buf, 0);
    spb = (sp_block*)buf;

    if(spb->magic_num == MAGIC_NUMBER)  // a file system exists
    {
        printf("Unkown file system found\n");
        do
        {
            printf("Format disk and rebuild a sucking file system?(y/n) ");
            format_op = getchar();
        }while(format_op != 'y' && format_op != 'n');
        getchar();  // get enter in buffer

        if(format_op == 'y')     // format disk and rebuild a sucking file system
        {
            FILE* tmp = fopen("disk","w");
            for(int32_t i = 0; i < get_disk_size(); i++)
            {
                fputc(0,tmp);
            }
            fclose(tmp);
            init_file_system();
            printf("Formatting finished, good luck and have fun!\n");
        }
    }
    else
    {
        init_file_system();
        printf("First starting up. Build a file system\n");
    }
    free(buf);
}